#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[50000];

int main()
{
	ll t[50000],w[50000];
  ll ts,n;
  cin>>ts>>n;
   for(int i=1;i<=n;i++)
   cin>>t[i]>>w[i];
  for(int i=1;i<=n;i++)
  {
  	int times=ts/t[i];
  	for(int j=ts;j>=t[i];j--)
  	{
	  	for(int mul=1;mul<=times;mul++)
	  	{
		  	if(j>=mul*t[i])
		  	{
			  	f[j]=max(f[j],f[j-t[i]*mul]+w[i]*mul);
			}
		  }
	  }
  }
  
  cout<<f[ts];
}
